import java.util.Scanner;

public class Main {
    int[] a;
    public int climbStairs(int n) {
        a = new int[n + 1];
        return f(n);
    }
    public int f(int n) {
        if (a[n] > 0) {
            return a[n];
        }
        if (n == 1 || n == 0) {
            return 1;
        }
        a[n] = f(n - 1) + f(n - 2);
        return a[n];
    }
}
